/*
 * @Author: szx
 * @Date: 2021-11-05 10:46:48
 * @LastEditTime: 2021-11-05 11:07:10
 * @Description:
 * @FilePath: \leetcode\1-99\77\77.cpp
 */

#include <iostream>
#include <vector>
using namespace std;

class Solution {
   public:
    vector<int> res;
    vector<vector<int>> ans;
    vector<vector<int>> combine(int n, int k) {
        dfs(1, n, k);
        return ans;
    }
    void dfs(int cur, int n, int k) {
        if (res.size() + n - cur + 1 < k) {
            return;
        }
        if (res.size() == k) {
            ans.emplace_back(res);
            return;
        }
        res.emplace_back(cur);
        dfs(cur + 1, n, k);
        res.pop_back();
        dfs(cur + 1, n, k);
    }
};